package com.leetcode.list;

import java.util.ArrayList;
import java.util.List;

public class SortList {
    public ListNode sortList(ListNode head) {
        // 自底向上归并排序
        if (head == null || head.next == null) {
            return head;
        }
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        for (int sublen = 1; sublen < len; sublen <<= 1) {
            ListNode pre = dummy;
            cur = pre.next;
            while (cur != null) {
                ListNode head1 = cur;
                ListNode head2 = cut(head1, sublen);
                ListNode next = cut(head2, sublen);
                ListNode merged = merge(head1, head2);
                pre.next = merged;
                while (pre.next != null) {
                    pre = pre.next;
                }
                cur = next;
            }
        }
        return dummy.next;
    }

    public ListNode cut(ListNode head, int size) {
        // 截取当前片段，返回下一片段起点;
        ListNode p = head;
        for (int i = 1; i < size && p != null && p.next != null; i++) {
            p = p.next;
        }
        ListNode q = null;
        if (p != null) {
            q = p.next;
            p.next = null;
        }
        return q;
    }
    
    public ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
                cur = cur.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
                cur = cur.next;
            }
        }
        if (head1 != null) {
            cur.next = head1;
        }
        if (head2 != null) {
            cur.next = head2;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        int[] nums = new int[] { -1, 5, 3, 4, 0 };
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int num : nums) {
            cur.next = new ListNode(num);
            cur = cur.next;
        }
        ListNode res = new SortList().sortList(dummy.next);
        List<Integer> resList = new ArrayList<>();
        // resList.set(index, element)
        ListNode p = res;
        while (p != null) {
            resList.add(p.val);
            p = p.next;
        }
        System.out.println(resList.toString());
    }
}
